/*
 * File: graph.c
 *
 * Integrantes:
 * @author Jormar Arellano   (05-37840) <jormar.arellano@gmail.com>
 * @author Sabrina Fernández (05-38163) <sabrinamfm@gmail.com>
 */

#include "graph.h"
#include "util.h"

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

Graph *parser_graph(char* f_name) {
	int vertex_number = 0;      // DEPRECATED: se puede reutilizar e1, e2
	int edge_number = 0;        // DEPRECATED: se puede reutilizar e1, e2
	FILE *myFile = NULL;        // File descriptor
	char *line = NULL;          // Buffer de línea
    size_t nline = 0;           // Numero de caracteres en la línea leída
	Graph *graph = NULL;        // Grafo
    int ecount = 0;             // Contador para número de aristas leídas
    int line_count = 0;         // Va contando el número de líneas leído
    int e1, e2;                 // Usados para crear las aristas
    int i;

	// Abrimos el archivo
	if( !(myFile = fopen(f_name, "r")) ) {
		fprintf(stderr, "Hubo un problema con el archivo \"%s\" y no pudo abrirse. \n", f_name);
        exit(EXIT_FAILURE);
	}

    /// Parseamos el archivo. El protocolo es muy simple
    /// c string         Son comentarios
    /// p edge %V %E     Indica el numero de nodos y aristas en el grafo
    /// e %N1 %N2        Indica una arista que va de %N1 a %N2
    while( getline(&line, &nline, myFile) != -1 ) {
        line_count++;

        switch(line[0]){
            case 'e':
                sscanf(line, "e %d %d", &e1, &e2);
                addEdge(graph, e1-1, e2-1);
                ecount++;
                break;

            case 'p':
                // Se crea el grafo con las dimensiones especificadas
                sscanf(line, "p edge %d %d", &vertex_number, &edge_number);

                // DEBUG
                PRINT("Las dimensiones del grafo son ")
                DEBUG("%d", vertex_number)
                DEBUG("x%d\n", edge_number)
                graph = newGraph(vertex_number, edge_number, 0);

                for(i=0; i<graph->vertex_number; i++){
                    arraylist_append(graph->vertex, newVertex(i+1));
                }
                break;

            case 'c':
                // Los comentarios se ignoran
                continue;

            default:
                // No pueden haber lineas vacias
                fprintf(stderr, " >> WARNING: La linea %d no encaja en el formato de archivo.\n", line_count);
                continue;
        }
    }
    if(line) free(line);

    // Verificacion de numero de vertices
    if(graph && ecount != graph->edge_number)
        fprintf(stderr, ">> WARNING: Se leyeron %d aristas de las %d esperadas.\n", ecount, graph->vertex_number);

    return graph;
}

Vertex *newVertex(int id) {
    Vertex *v = (Vertex *) malloc(sizeof(Vertex));

    v->id = id;
    v->color = 0;
    v->saturationDegree = 0;
    v->neighbors = arraylist_new(0);
    v->inConflict = 0;

    return v;
}

Vertex *cloneVertex(const Vertex *v, int withNeighbors) {
    int i;
    Vertex *v2 = newVertex(v->id);

    v2->color = v->color;
    v2->neighbors = arraylist_new(v->neighbors->length);
    v2->saturationDegree = v->saturationDegree;

    if(withNeighbors != 0){
        for(i=0; i<v->neighbors->length; i++)
            arraylist_append(v2->neighbors, v->neighbors->data[i]);
    }

    return v2;
}

int compareVertexById(ArrayListValue v1, ArrayListValue v2) {
    Vertex *va = (Vertex *)v1;
    Vertex *vb = (Vertex *)v2;

    if(va->id < vb->id) return -1;
    if(va->id > vb->id) return 1;
    else return 0;
}

int compareVertexByNeighbor(ArrayListValue v1, ArrayListValue v2) {
    Vertex *va = (Vertex *)v1;
    Vertex *vb = (Vertex *)v2;

    if(va->neighbors->length < vb->neighbors->length) return -1;
    if(va->neighbors->length > vb->neighbors->length) return 1;
    else return 0;
}

int compareVertexByGrasp_Totalu(ArrayListValue v1, ArrayListValue v2) {
    Vertex *va = (Vertex *)v1;
    Vertex *vb = (Vertex *)v2;

    if(va->_grasp_Totalmark_u < vb->_grasp_Totalmark_u) return -1;
    if(va->_grasp_Totalmark_u > vb->_grasp_Totalmark_u) return 1;
    else return 0;
}

void printVertex(Vertex *v) {
    int i;

    printf("Vertex %3d, color %3d [", v->id, v->color);
    for(i=0; i<v->neighbors->length; i++) {
        printf(" %d ", ((Vertex*)v->neighbors->data[i])->id);
    }
    printf("]\n");
}

int getNumConflict(Vertex *v) {
    int i, resp;
    Vertex *vaux;

    for(i=0, resp=0; i<v->neighbors->length; i++) {
        vaux = v->neighbors->data[i];
        if(vaux->color == v->color) resp++;
    }

    return resp;
}

int vertexHasConflict(Vertex *v, int color) {
    int i;
    Vertex *vaux;

    if(color == 0) color = v->color;

    for(i=0; i<v->neighbors->length; i++) {
        vaux = v->neighbors->data[i];

        if(vaux->color == color) {
            return 1;
        }
    }

    return 0;
}

void freeVertex(Vertex *v) {
    arraylist_free(v->neighbors);
    free(v);
}

Graph *newGraph(int vertex_number, int edge_number, int cost) {
    Graph *graph = (Graph *) malloc(sizeof(Graph));

    graph->vertex_number = vertex_number;
    graph->edge_number = edge_number;
    graph->cost = cost;
    graph->vertex =  arraylist_new(vertex_number);
    graph->Vcolors =  arraylist_new(0);
    graph->conflictVertex = arraylist_new(0);
    graph->penaltyCost = penaltyCost(graph);

    return graph;
}

Graph *cloneGraph(const Graph *graph) {
    int i, j;
    Vertex *v, *vaux, *vret;
    Graph *ret = newGraph(graph->vertex_number, graph->edge_number, graph->cost);

    // Primero hay que crear todos los vertices
    for(i=0; i<graph->vertex->length; i++) {
        v = graph->vertex->data[i];
        arraylist_append(ret->vertex, newVertex(v->id));
    }

    // Creamos las relaciones entre los vertices
    for(i=0; i<graph->vertex->length; i++) {
        v = graph->vertex->data[i];
        vret = ret->vertex->data[i];

        for(j=0; j<v->neighbors->length; j++) {
            vaux = v->neighbors->data[j];
            arraylist_append(vret->neighbors, ret->vertex->data[vaux->id-1]);
        }
    }

    // Coloreamos el grafo
    for(i=0; i<graph->vertex->length; i++) {
        v = graph->vertex->data[i];
        setColor(ret, ret->vertex->data[i], v->color);
    }

    return ret;
}

void addEdge(Graph *graph, int v1, int v2) {
    arraylist_append(((Vertex *)graph->vertex->data[v1])->neighbors, graph->vertex->data[v2]);
    arraylist_append(((Vertex *)graph->vertex->data[v2])->neighbors, graph->vertex->data[v1]);
}

void addConflictNode(Graph *graph, Vertex *v) {

    if(!v->inConflict) {
        arraylist_append(graph->conflictVertex, v);
        v->inConflict = 1;
    }
}

void removeConflictNode(Graph *graph, Vertex *v) {
    int i;

    if(v->inConflict) {
        i = arraylist_index_of(graph->conflictVertex, compareVertexById, v);
        arraylist_remove(graph->conflictVertex, i);
        v->inConflict = 0;
    }
}

void setColor(Graph *graph, Vertex *v, int color) {
    int i;
    ArrayList *vertexList;
    Vertex *vaux;
	//int j, hasConflict; Vertex *vaux2;
    
    if(0<color) {
        // Hay que sacarlo de su conjunto de colores actual
        if(v->color != 0) {
            vertexList = graph->Vcolors->data[v->color-1];
            i = arraylist_index_of( vertexList, compareVertexById, v);

            // TODO: quitar esta verificacion por rendimiento
            /*if(i<0){
                perror("Falla de integridad en Vcolors del grafo");
                exit(EXIT_FAILURE);
            }*/

            arraylist_remove(vertexList, i);
        }

        // Si es necesario, crear conjunto de colores
        while(graph->Vcolors->length < color) arraylist_append(graph->Vcolors, arraylist_new(0));

        // Se incluye en su nuevo conjunto de colores
        arraylist_append(graph->Vcolors->data[color-1], v);

        // Cambiamos su color
        v->color = color;

        // Eliminamos los conflictos. Solo el nodo y sus vecinos pueden caer en conflicto.
        for(i=0; i<v->neighbors->length; i++) {
            vaux = v->neighbors->data[i];

            if(vertexHasConflict(vaux, 0)) {
                addConflictNode(graph, vaux);
            } else {
                removeConflictNode(graph, vaux);
            }
        }
        if(vertexHasConflict(v, 0)) {
            addConflictNode(graph, v);
        } else {
            removeConflictNode(graph, v);
        }
    }
}

void removeDeadColors(Graph *graph) {
    int i, j;
    int hay;
    ArrayList *vcolors;

    for(i=0; i<graph->Vcolors->length; i++) {
        vcolors = graph->Vcolors->data[i];

        if(vcolors->length == 0) {
            // Buscamos siguiente lista llena de vertices
            for(j=i+1, hay=0; !hay && j<graph->Vcolors->length; j++) {
                vcolors = graph->Vcolors->data[j];
                if(vcolors->length != 0) hay = 1;
            }

            // Si no hay lista de vertices, entonces ya todos estan agrupados
            if(!hay) return;

            // Movemos los vertices.
            while(vcolors->length) {
                setColor(graph, vcolors->data[0], i+1);
            }
        }
    }

    // Eliminamos los colores finales que no tengan vertices
    for(
            i = graph->Vcolors->length-1;
            !((ArrayList*)graph->Vcolors->data[i])->length;
            i--)
    {
        arraylist_free(graph->Vcolors->data[i]);
        arraylist_remove(graph->Vcolors, i);
    }
}

void discolorGraph(Graph *graph){
    int i;
    Vertex *v;
    if (graph != NULL) {
        for (i=0; i<graph->vertex->length; i++) {
            v = graph->vertex->data[i];
            v->color = 0;
            v->saturationDegree = 0;
            v->inConflict = 0;
        }

        // Eliminamos las particiones de colores
        for (i=0; i<graph->Vcolors->length; i++) {
            arraylist_free(graph->Vcolors->data[i]);
        }
        arraylist_clear(graph->Vcolors);

        // Ya no hay conflictos
        arraylist_clear(graph->conflictVertex);
    }
}

void printGraph(Graph *graph) {
    int i;

    printf("PrintGraph (vertex: %d, Edges: %d)\n", graph->vertex_number, graph->edge_number);
    for(i=0; i<graph->vertex->length; i++) {
        printVertex(graph->vertex->data[i]);
    }
}

void printGraphColors(Graph *graph) {
    int i, j;
    ArrayList *vcolor;

    printf(" >> Vertices particionados por Colores:\n");
    for(i=0; i<graph->Vcolors->length; i++) {
        vcolor = graph->Vcolors->data[i];
        if(vcolor->length != 0) {
            printf(" Color %d: [", i+1);
            for(j=0; j<vcolor->length; j++) {
                printf(" %d ", ((Vertex*)vcolor->data[j])->id);
            }
            printf("]\n");
        }
    }
}

void printGraphConflicts(Graph *graph) {
    int i;
    Vertex *v;

    printf(" >> Vertices en conflicto:\n[");
    for(i=0; i<graph->conflictVertex->length; i++) {
        v = graph->conflictVertex->data[i];

        printf(" %d(%d) ", v->id, v->color);
    }
    printf("]\n");
}

int getTotalColor(Graph *graph) {
    int i, colors;
    ArrayList *c;

    for(i=0, colors=0; i<graph->Vcolors->length; i++) {
        c = graph->Vcolors->data[i];
        if( c->length != 0) colors++;
    }

    return colors;
}

void colorMatch(Graph *g1, const Graph *g2) {
    int i;
    Vertex *v;

    for(i=0; i<g2->vertex->length; i++) {
        v = g2->vertex->data[i];
        setColor(g1, g1->vertex->data[i], v->color);
    }
}

void freeGraph(Graph *graph) {
    int i;
    if (graph != NULL) {
        for (i=0; i<graph->vertex->length; i++) {
            freeVertex( (Vertex *) graph->vertex->data[i] );
        }
        arraylist_free(graph->vertex);

        for (i=0; i<graph->Vcolors->length; i++) {
            arraylist_free(graph->Vcolors->data[i]);
        }
        arraylist_free(graph->Vcolors);
        arraylist_free(graph->conflictVertex);
        free(graph);
    }
}

int isFeasibleSolution(Graph *graph) {
    int i, j;
    Vertex *v = NULL, *neighbor = NULL;

    for(i=0; i<graph->vertex->length; i++) {
        v = graph->vertex->data[i];
        for(j=0; j<v->neighbors->length; j++) {
            neighbor = v->neighbors->data[j];
            if(v->color == neighbor->color) return 0;
        }
    }

    return 1;
}

long penaltyCost(Graph *graph) {
    int i, j;
    long penaltyCost = 0, Ei, Ci;
    ArrayList *vcolors;
    Vertex *v;

    for(i=0; i<graph->Vcolors->length; i++) {
        vcolors = graph->Vcolors->data[i];
        // Calculo de vertices en Ci
        Ci = vcolors->length;
        // Calculo de vertices en conflicto Ei
        for(j=0, Ei=0; j<graph->conflictVertex->length; j++) {
            v = graph->conflictVertex->data[j];
            if(v->color == i+1) Ei++;
        }
        penaltyCost += 2*Ci*Ei - Ci*Ci;
    }

    return penaltyCost;
}
